<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
           和题2区别：每一笔交易完成，都需要扣除手续费。
           相似点：可以无限次交易；必须卖出股票后再买入
         * 输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
         * 输出：8
         * 在此处买入 prices[0] = 1
           在此处卖出 prices[3] = 8
           在此处买入 prices[4] = 4
           在此处卖出 prices[5] = 9
           总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
         * 
         * 输入: prices = [1,3,7,5,10,3], fee = 3
         * 输出: 6
         * 解释: 
         * 在此处买入，prices[0] = 1
         * 在此处卖出，prices[2] = 7
         * 在此处买入，prices[3] = 5
         * 在此处卖出，prices[4] = 10
         * 总利润: ((7 - 1) - 3) + ((10 - 5) - 3) = 6
         * 
        */
        /* 
            时间：O(n) prices的长度
            空间：O(n) prices的长度，二维数组可以忽略不计
        */
        var maxProfit = function(prices, fee) {
            const dp = new Array(prices.length).fill([0, 0])
            dp[0][0] = -prices[0]

            for (let i = 1; i < prices.length; i++) {
                dp[i] = [
                    Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]),
                    // 唯一区别：卖出时扣除手续费
                    Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)
                ]
            }
            console.log(dp, 'dp');
            return dp[prices.length - 1][1]
        };
        console.log(maxProfit([1, 3, 2, 8, 4, 9], 2));
        console.log(maxProfit([1, 3, 7, 5, 10, 3], 3));
        // console.log(maxProfit([7,6,4,3,1]));
    </script>
</body>

</html>